[题解]LG4212 外太空问题

LG4212 外太空问题

https://www.luogu.com.cn/problem/P4212

最大团问题。

最大团问题可以用 折半搜索+状压 DP 解决。但是随机化更加方便。

考虑普通的贪心。动态加入点。加入这个加入的点和以前所有加入的点都有连边，那么我们就选，否则就不选。第一个点必选。

贪心的正确性很低。所以我们用随机化，多随机几次序列的顺序即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=59;

int n,u,v,ans,tot,id[N];
bool e[N][N];
vector<int>ch;

void solve() {
	ch.clear(), tot=0;
	random_shuffle(id+1,id+n+1);
	rep(i,1,n) {
		bool b=1;
		if(ch.size()) rep(j,0,ch.size()-1) b&=e[id[i]][ch[j]];
		if(b) ch.push_back(id[i]), tot++;
	}
	ans=max(ans,tot);
}

int main() {
	srand(time(0));
	scanf("%d",&n);
	while(scanf("%d%d",&u,&v)!=EOF) e[u][v]=e[v][u]=1;
	rep(i,1,n) id[i]=i;
	rep(t,1,100000) solve();
	printf("%d\n",ans);
	return 0;
}